package 力扣算法练习.main1.part1;

import java.nio.charset.StandardCharsets;
import java.util.HashSet;
import java.util.Set;

public class day2 {

    /*
    给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的 中位数 。
    算法的时间复杂度应该为 O(log (m+n)) 。
    https://leetcode.cn/problems/median-of-two-sorted-arrays
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //在一个循环内同时遍历两个数组,每次取两个中小的那个
        int index1 = 0, index2 = 0, length1 = nums1.length, length2 = nums2.length;
        int temp1 = 0, temp2 = 0, i = 0;
        int centre = (length1 + length2) / 2 + 1;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] <= nums2[index2]) {
                temp2 = temp1;
                temp1 = nums1[index1++];
            } else {
                temp2 = temp1;
                temp1 = nums2[index2++];
            }
            if (++i == centre) {
                break;
            }
        }
        //可能经过了循环还是没走到中间
        if (i != centre) {
            if (index1 == length1) {
                //数组1中的所有值已经遍历完,继续遍历数组2
                while (index2 < length2) {
                    temp2 = temp1;
                    temp1 = nums2[index2++];
                    if (++i == centre) break;
                }
            } else {
                //数组2中的所有值已经遍历完,继续遍历数组1
                while (index1 < length1) {
                    temp2 = temp1;
                    temp1 = nums1[index1++];
                    if (++i == centre) break;
                }
            }

        }
        if ((length1 + length2) % 2 == 0) {
            return (temp1 + temp2) / 2.0;
        } else return temp1 / 1.0;
    }


    /*
    给你一个字符串 s，找到 s 中最长的回文子串。
    https://leetcode.cn/problems/longest-palindromic-substring/
     */
    //如果提供的字符全都一样时候没办法通过
/*    public  String longestPalindrome(String s) {
        if (s.length()==0)return s;
        char[] chars = s.toCharArray();
        StringBuilder temp=new StringBuilder();
        StringBuilder result=new StringBuilder();
        char tchar='0';
        int end;
        Set<Character> set=new HashSet<>();
        for (int i = 0; i <chars.length; i++) {
            end=i;
            while (end<chars.length){
                if (tchar=='0'){
                    tchar=chars[end];
                }else{
                    if(chars[end]==tchar){
                        if (expand(chars,i,end)){
                            //到这里说明是回文将其存入temp中
                            for (int j = i; j <=end; j++) {
                                temp.append(chars[j]);
                            }
                            if(temp.length()>result.length())result=temp;
                            temp=new StringBuilder();
                        }
                            tchar='0';
                            break;
                    }
                }
                if (end==chars.length-1)tchar='0';
                end++;
            }
        }
        //到这里如果结果字符转中还没有元素说明给的字符串没有重复的元素
        if (result.length()==0)return chars[0]+"";
        return result.toString();
    }
    //判断是不是回文字符串
    private boolean expand(char[] s,int left,int right){
        while (left<=right){
            if (s[left++]!=s[right--])return false;
        }
        return true;
    }*/

    //官方解
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}
